package com.wc.alorithm_blue_bridge._数学知识.快速幂.Q1181;

import java.util.Scanner;

/**
 * @Author congege
 * @Description 数的幂次
 * https://www.lanqiao.cn/problems/1181/learning/?page=2&first_category_id=1&sort=students_count&second_category_id=8
 * @Date Created in 2023/11/7-9:50
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        int n, m, p;
        Main main = new Main();
        StringBuffer res = new StringBuffer();
        while (t-- > 0) {
            n = sc.nextInt();
            m = sc.nextInt();
            p = sc.nextInt();
            res.append(main.quickCal(n, m, p));
            res.append('\n');
        }
        System.out.print(res);
    }

    public long quickCal(long n, long m, long p) {
        if (m == 1) {
            return n % p;
        }

        long qk = quickCal(n, m / 2, p);
        long ans = qk * qk % p;
        if (m % 2 == 1) {
            ans = ans * n % p;
        }
        return ans;
    }
}
